theory
A problem with a yes/no answer. Determining whether some potential solution to a question is actually a solution or not. E.g. "Is 43669" a prime number?". This is in contrast to a "search problem" which must find a solution from scratch, e.g. "What is the millionth prime number?".
See decidability.
(1996-05-03)
for a class of questions in mathematics and formal logic, the problem of finding, after choosing any question of the class, an algorithm or repetitive procedure that will yield a definite answer, "yes" or "no," to that question. The method consists of performing successively a finite number of steps determined by preassigned rules. In particular, the term is used for such procedures for finding whether-in a particular logistic system, logical calculus, or formal mathematical system-some given "well-formed formula" (generated in accordance with established formation rules) is or is not provable as a theorem of the system